#include <vector>
using namespace std;
int rob(vector<int> &nums) {
  // 状态转移方程 dp[i] = max(dp[i-1], dp[i-2]+cur[i])
  int len = nums.size();
  vector<int> dp(len);
  dp[0] = nums[0];
  if (len == 1)
    return dp[0];
  dp[1] = max(dp[0], nums[1]);
  if (len == 2)
    return dp[1];
  if (len < 3)
    return dp[len - 1];
  for (int i = 2; i < len; ++i) {
    dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[len - 1];
}